/******
* alignment.cpp
*
* Takes two sequences of comparables and aligns them to best comparison.
* Returns pairs of positions of comparables of maximal alignment that do not match.
******/

#include "NumberComparable.h"
#include "SpecialComparable.h"
#include "WSComparable.h"
#include "GeneralComparable.h"
#include <utility>
#include <vector>

template<class T> std::vector<std::pair<int, int> > alignComparables(std::vector<T> a, std::vector<T> b)
{
	int i, j, iAlign;
	int minI,minJ;
	int dist, minDist, tmp;
	std::vector<T> aAlign,bAlign;    //aligned comparables
	int aLen = a.size();
	int bLen = b.size();
	vector< vector< int > > trace(bLen+1);       //trace matrix
	vector< vector< int > > distance(bLen+1);    //distance matrix
	std::vector<std::pair<int,int> > c;
	
	vector<int> temp;

	for (i = 0; i <= bLen; i++)
	{
		distance[i].reserve(aLen+1);
		trace[i].reserve(aLen+1);
		distance[i][0]=0;
		trace[i][0]=0;
	}

	for (j = 0; j <= aLen; j++)
	{
		
		distance[0][j]=0;
		trace[0][j]=0;
	}

	minDist = 0;
	minI = 0;
	minJ = 0;
	
	for (i = 1; i <= aLen; i++)
	{
		for (j=1; j <= bLen; j++)
		{
			dist = 0;
			trace[i][j] = 0;
			if (a[i-1].compare(b[j-1])) tmp = distance[i-1][j-1]-10;   //match case (heuristic -10)
			else tmp = distance[i-1][j-1]+7;                           //mismatch case (+7)
			if (tmp < dist)
			{
				dist = tmp;
				trace[i][j] = 3;
			}
	
			tmp = distance[i-1][j]+4;                                  //gap in b (+4)
			if (tmp < dist)
			{
				dist = tmp;
				trace[i][j] = 1;
			}

			tmp = distance[i][j-1]+4;                                  //gap in a (+4)
			if (tmp < dist)
			{
				dist = tmp;
				trace[i][j] = 2;
			}
			
			distance[i][j]=dist;
			
			if (dist < minDist)
			{
				minDist = dist;
				minI = i;
				minJ = j;
			}
		}	
	}

	//create best aligned sequences in reverse order
	
	i = aLen;
	j = bLen;
	iAlign = 0;        

	while (i > minI)                  //b has gaps on end
	{
		bAlign.push_back(T());
		aAlign.push_back(a[i-1]);
		i--;
		iAlign++;
	}

	while (j > minJ)                  //a has gaps on end
	{
		bAlign.push_back(b[j-1]);
		aAlign.push_back(T());
		j--;
		iAlign++;
	}

	//follow trace matrix, placing gaps properly

	while (trace[i][j] != 0)
	{
		if (trace[i][j] == 3)
		{
			bAlign.push_back(b[j-1]);
			aAlign.push_back(a[i-1]);
			i--;
			j--;
			iAlign++;
		}
		
		else if (trace[i][j] == 2)
		{
			bAlign.push_back(b[j-1]);
			aAlign.push_back(T());
			j--;
			iAlign++;
		}

		else if (trace[i][j] == 1)
		{
			bAlign.push_back(T());
			aAlign.push_back(a[i-1]);
			i--;
			iAlign++;
		}
	}

	//misaligned beginning
		
	while (i > 0)
	{
		bAlign.push_back(T());
		aAlign.push_back(a[i-1]);
		i--;
		iAlign++;
	}
	
	while (j > 0)
	{
		bAlign.push_back(b[j-1]);
		aAlign.push_back(T());
		j--;
		iAlign++;
	}

	//return only the different pairs in reverse order

	for (i = iAlign-1; i>=0; i--)
	{
        	if (!(aAlign[i].compare(bAlign[i])))
		   c.push_back(std::make_pair(aAlign[i].getPosition(),bAlign[i].getPosition()));
	}

	return c;
}